package FFT;

import java.util.ArrayList;
import java.util.Random;
import fingerStore.ShazamHash;
/**
 * Created by mengwei666 on 2016/11/8.
 */
public class FingerPrint {
    // DO NOT write FFT.WINDOW_SIZE / 44100, it equals to 0 forever!!
    public static final double scaling = Fft.WINDOW_SIZE / 44100.0;
    public static final int interval_num = 3 ;
    public static final int N = 3;

    private ArrayList<int[]> constel_data = new ArrayList<>();
    private int id;

    /**
     * For songs about to add into DB
     * @param id
     */
    public FingerPrint(int id) {
        this.id = id;
    }

    /**
     * For songs about to be searched
     */
    public FingerPrint() {
        this.id = -1;
    }

    /**
     * Append a column of frequency peaks to the constellation map.
     * A frequency peak is a frequency value whose amplitude is the highest among
     * all frequencies in a frequency interval.
     *
     * @param freqDomain The frequency domain generated by FFT.
     */
    public void append(double[] freqDomain) {
        int[] freqPeaks = new int[N];
        freqDomain = Fft.fft(freqDomain);
        double[] freqDomain0 = new double[freqDomain.length/8];
        //double[] confirmdouble = new double[freqDomain0.length];
        for(int j =0;j<freqDomain0.length;++j){
            freqDomain0[j] = freqDomain[j];
            //confirmdouble[j] = freqDomain0[j];
        }
        /*Arrays.sort(confirmdouble);
        System.out.println(confirmdouble[confirmdouble.length-1]+" "+
        confirmdouble[confirmdouble.length-2]+" "+
        confirmdouble[confirmdouble.length-3]);*/
        quickSelect(freqDomain0,0,freqDomain0.length-1,3);//只对前1/8提取指纹
        for(int i=0;i<freqDomain0.length;++i){
            if(freqDomain[i] == freqDomain0[0])
                freqPeaks[0] = (i+1);
            else if(freqDomain[i] == freqDomain0[1])
                freqPeaks[1] = (i+1);
            else if(freqDomain[i] == freqDomain0[2])
                freqPeaks[2] = (i+1);
        }

        /**
         * TODO: Either find N frequencies with the highest amplitude(energy),
         * or find the frequency with the max energy within each interval.
         */

        constel_data.add(freqPeaks);
    }
    //得到k个最大数的快速选择算法
    public static double[] quickSelect(double[] arr,int l,int h,int k){
        int l_temp = l;
        int h_temp = h;

        int q =randomizedPartition(arr,l,h);

        if(q == k-1)
            return arr;
        else if(q<k-1)
            return quickSelect(arr,q+1,h_temp,k);
        else
            return quickSelect(arr,l_temp,q-1,k);

    }

    public static int randomizedPartition(double[] arr,int l,int h){
        int i = new Random().nextInt(h-l+1)+l;
        swap(arr,i,h);//交换枢纽元，由于partition默认选择最后一位
        return partition(arr,l,h);

    }

    public static int partition(double[]arr,int l,int h){
        int i = l-1;
        double key = arr[h];//partition默认选择最后一位为枢纽元，所以需要随机选择函数交换顺序
        for(int j=0;j<h;j++){
            if(arr[j]>=key && i<j){
                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,i+1,h);//restore pivot  交换顺序后 再交换回原来的顺序
        return i+1;
    }

    public static void swap(double[] arr,int l,int h){
        double temp = arr[l];
        arr[l] = arr[h];
        arr[h] = temp;

    }
    /**
     * Generate fingerprints using Combinational Hash.
     * For each frequency peak, generate 6 fingerprints with its 6 successors.
     *
     * @return
     */


    public ArrayList<ShazamHash> combineHash() {
        if (constel_data.size() < 3)
            throw new RuntimeException("Too few frequency peaks");
        ArrayList<ShazamHash> hashes = new ArrayList<>();
        for (int i = 0; i < constel_data.size() - 2; ++i) {
            for (int k = 0; k < interval_num; ++k) {

                // "Combine" with all peak frequencies inside its next two frames.
                for (int j = 1; j <= 2; ++j) {
                    for (int kk = 1; kk < interval_num; ++kk) {
                        ShazamHash hash = new ShazamHash();
                        hash.f1 = (short) constel_data.get(i)[k];
                        hash.f2 = (short) constel_data.get(i + j)[kk];
                        hash.dt = (short) j;
                        hash.finger_id = (hash.dt<<18) | (hash.f1<<9) | hash.f2;
                        hash.offSet = (short)i;
                        hash.song_id = (short)id;
                        hashes.add(hash);
                    }
                }
            }
        }
        return hashes;
    }
}
